'''
背包问题
    一个小偷在某个商店发现有n个商品,第i个商品价值vi元,重wi千克.他希望拿走的价值尽量高,但它的背包最多只能容纳W千克的东西.
    他应该拿走哪些商品?
        0-1背包:对于一个商品,小偷要么把它完整拿走,要么留下.不能只拿走一部分,或把一个商品拿走多次.(商品为金条)
        分数背包:对于一个商品,小偷可以拿走其中任意一部分(商品为金砂)
'''

# goods = [(60,10),(120,30),(100,20)]  # 每个元组表示商品的(价格,重量)
# goods.sort(key = lambda x: x[0]/x[1],reverse = True)
# print(goods)
# def fractional_backpack(goods,w):
#     print("函数内的goods顺序：", goods)  # 新增打印
#     m = [0 for _ in range(len(goods))]
#     total_v = 0
#     for i,(price,weight) in enumerate(goods):
#         if w >= weight:
#             m[i] = 1
#             w -= weight
#             total_v += price
#         else:
#             m[i] = w/weight
#             total_v += price * m[i]
#             w = 0
#             break
#     return m,total_v
#
# print(fractional_backpack(goods,50))

goods = [(60,10),(120,30),(100,20)]
goods.sort(key = lambda x : x[0]/x[1],reverse=True)
print(goods)
def fractional_backpack(goods,w):
    m = [0 for _ in range(len(goods))]
    total_v = 0
    for i ,(price,weight) in enumerate(goods):
        if w > weight:
            m[i] = weight
            w -= weight
            total_v += price
        elif w < weight:
            m[i] = w
            total_v += price*(w/weight)
            w = 0
    return m,total_v

print(fractional_backpack(goods,50))
